//class Solution {
//public:
//    vector<int> diStringMatch(string s) {
//        int left = 0, right = s.size();
//        vector<int> ret(right + 1);
//        int i = 0;
//        for (auto ch : s)
//            if (ch == 'I')
//                ret[i++] = left++;
//            else
//                ret[i++] = right--;
//        ret[i] = left;
//        return ret;
//    }
//};



//class Solution {
//public:
//    int findContentChildren(vector<int>& g, vector<int>& s) {
//        sort(g.begin(), g.end());
//        sort(s.begin(), s.end());
//
//        int ret = 0;
//        for (int i = g.size() - 1, j = s.size() - 1; i >= 0 && j >= 0;)
//        {
//            if (s[j] >= g[i])
//                ret++, j--, i--;
//            else
//                i--;
//        }
//        return ret;
//    }
//};




//class Solution {
//public:
//    string optimalDivision(vector<int>& nums) {
//        string ret;
//        int n = nums.size();
//        if (n == 1)
//            ret = to_string(nums[0]);
//        else if (n == 2)
//        {
//            ret += to_string(nums[0]) + '/' + to_string(nums[1]);
//        }
//        else
//        {
//            for (int i = 0; i < n; i++)
//            {
//                if (i == 1)
//                    ret += '(';
//                ret += to_string(nums[i]) + '/';
//            }
//            ret[ret.size() - 1] = ')';
//        }
//        return ret;
//    }
//};


//class Solution {
//public:
//    bool canJump(vector<int>& nums) {
//        int n = nums.size(), left = 0, right = 0;
//        while (left <= right)
//        {
//            if (right >= n - 1) return true;
//            int maxpos = 0;
//            for (int i = left; i <= right; i++)
//                maxpos = max(maxpos, nums[i] + i);
//            left = right + 1;
//            right = maxpos;
//        }
//        return false;
//    }
//};


class Solution {
public:
    int jump(vector<int>& nums) {
        int n = nums.size(), ret = 0;
        if (n == 1) return 0;
        for (int left = 0, right = 0; right < n;)
        {
            int maxpos = 0; ret++;
            while (left <= right)
            {
                maxpos = max(maxpos, left + nums[left]);
                left++;
                if (maxpos >= n - 1)
                    return ret;
            }
            right = maxpos;
        }
        return -1;
    }
};